#include <iostream>
#include <fstream>
#include <ctime>
#include <string>
#include <windows.h>
#include <psapi.h>
#include <process.h>

#include "DSTree.h"

#pragma comment(lib, "psapi.lib")

using namespace std;

const int MAXN = 0xfff00 + 10;
int array[MAXN];

int getMemoryInfo( DWORD processID );

void solve(ifstream *in, ofstream *out, ofstream *cen);
void solveData ();
void solveInsertData ();
void solveFindData ();
void solveUpdateData ();
void solveSearchData ();
void solveRemoveData ();

int main()
{
	solveData ();
	solveInsertData ();
	solveFindData ();
	solveUpdateData ();
	solveSearchData ();
	solveRemoveData();

    return 0;
}

void solve(ifstream *in, ofstream *out, ofstream *cen)
{
	int t;
	*in>>t;

	DSTree *dsTree = new DSTree();
	int test = 1;
	while (t--)
	{
		*out<<"case "<<test++<<":"<<endl;
		int n;
		*in>>n;
		for (int i = 0; i < n; i++)
		{
			*in>>array[i];
		}
		clock_t start = clock();
		dsTree->buildTree(array, n);
		int m;
		*in>>m;
		while (m--)
		{
			//dsTree->showTree();
			string str;
			*in>>str;
			if (!str.compare("insert")){
				int index, value;
				*in>>index>>value;
				dsTree->insert(index, value);
			}else if (!str.compare("update")){
				int index, value;
				*in>>index>>value;
				dsTree->update(index, value);
			}else if (!str.compare("updateInterval")){
				int left, right, value;
				*in>>left>>right>>value;
				dsTree->updateInterval(left, right, value);
			}else if (!str.compare("find")){
				int index;
				*in>>index;
				int ans = dsTree->find(index);
				*out<<ans<<endl;
			}else if (!str.compare("search")){
				int value;
				*in>>value;
				int ans = dsTree->search(value);
				*out<<ans<<endl;
			}else if (!str.compare("hide")){
				int left, right;
				*in>>left>>right;
				dsTree->hide(left, right);
			}else if (!str.compare("remove")){
				int index;
				*in>>index;
				dsTree->remove(index);
			}
		}
		int memory = getMemoryInfo(_getpid());
		dsTree->destroyTree();
		clock_t end = clock();

		*cen << memory <<"\t";
		*cen << (double)(end - start) / CLOCKS_PER_SEC <<endl;
		/*
		clog << memory <<"\t";
		clog << (double)(end - start) / CLOCKS_PER_SEC <<endl;*/
	}
	delete(dsTree);
	dsTree = NULL;
}

void solveData ()
{
	ifstream in("../data/inputDate.in");
	ofstream out("../data/ans.out");
	ofstream cen("../data/memory_time_ans.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

void solveInsertData ()
{
	ifstream in("../data/inputDate_all_insert.in");
	ofstream out("../data/ans_all_insert.out");
	ofstream cen("../data/memory_time_ans_all_insert.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

void solveFindData ()
{
	ifstream in("../data/inputDate_all_find.in");
	ofstream out("../data/ans_all_find.out");
	ofstream cen("../data/memory_time_ans_all_find.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

void solveUpdateData ()
{
	ifstream in("../data/inputDate_all_update.in");
	ofstream out("../data/ans_all_update.out");
	ofstream cen("../data/memory_time_ans_all_update.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

void solveSearchData ()
{
	ifstream in("../data/inputDate_all_search.in");
	ofstream out("../data/ans_all_search.out");
	ofstream cen("../data/memory_time_ans_all_search.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

void solveRemoveData ()
{
	ifstream in("../data/inputDate_all_remove.in");
	ofstream out("../data/ans_all_remove.out");
	ofstream cen("../data/memory_time_ans_all_remove.out");

	solve(&in, &out, &cen);

	out.close();
	in.close();
}

int getMemoryInfo( DWORD processID )
{
	int ans = 0;
	HANDLE hProcess;
	PROCESS_MEMORY_COUNTERS pmc;

	hProcess = OpenProcess(  PROCESS_QUERY_INFORMATION |
		PROCESS_VM_READ,
		FALSE, processID );
	if (NULL == hProcess)
		return ans;

	if ( GetProcessMemoryInfo( hProcess, &pmc, sizeof(pmc)) )
	{
		//ans = pmc.WorkingSetSize / 1024;
		ans = pmc.PagefileUsage / 1024;
	}

	CloseHandle( hProcess );
	return ans;
}